package com.xiaolin.algorithm.sort;

import java.util.Arrays;

/**
 * @ClassName BucketSort
 * @Description 桶排序是一种基于计数排序的一种排序方法
 * @Detail detail
 * @Author MyPC
 * @Date 2020/11/4
 * @Version 1.0
 */
public class BucketSort {
    public static void main(String[] args) {
        int arr[]={15,2,4,4,8,1,16,18,82,66};
        int[] sort = sort(arr);
        System.out.println(Arrays.toString(sort));
    }

    public static int[] sort(int[] arr){
        if(arr.length==0){
            return null;
        }
        // 自定义桶个数
        int bucketNum=5;
        // 步长(桶最多存放元素)
        int step = getStep(arr, bucketNum);
        // 数组元素的最小值
        int min = getMin(arr);
        // 桶数组
        int[][] bucketArr=new int[bucketNum][step];
        // 用于存放桶数组中每个桶的标志位置
        int[] flag=new int[bucketNum];
        // 1、遍历原数组，将原始存放到桶里
        for(int i=0;i<arr.length;i++){
            // 元素要放的桶的索引位置
            int index = (arr[i] - min) / step;
            // 桶无法存储更多的元素
            if(flag[index] == bucketArr[index].length){
                throw new ArrayIndexOutOfBoundsException("该数列不符合要求，导致桶索引越界，请选择其他排序方式");
            }
            bucketArr[index][flag[index]++]=arr[i];
        }
        // 2、遍历桶数组，对每个桶的元素进行排序、并把排序好的元素存储新数组中
        int[] newArr= new int[arr.length];
        // 新数组的标志索引
        int index=0;
        for(int i=0;i<bucketArr.length;i++){
            // 每个桶的元素个数
            int size=flag[i];
            if(size==0){
                // 如果桶元素个数为零，则跳过这次循环
                continue;
            }
            // 桶
            int[] bucket = bucketArr[i];
            // 2.1 插入排序进行元素的排序
            int temp=0;
            for (int j=1;j<size;j++){
               for(int k=j;k>0;k--){
                   if(bucket[k] < bucket[k-1]){
                       temp=bucket[k];
                       bucket[k]=bucket[k-1];
                       bucket[k-1]=temp;
                   }
               }
            }
            // 2.2 将排好序的元素存储新数组中
            // 桶数组的标志索引
            int index2=0;
            for(int t=index;t<index+size;t++){
                newArr[t]=bucket[index2++];
            }
            // 将桶元素存储之后，索引后移的步长是桶的元素个数
            index+=size;
        }
        list(bucketArr);
        return newArr;
    }

    /**
     * 遍历输出桶数组
     * @param bucketArr
     */
    private static void list(int[][] bucketArr){
        for (int i=0;i<bucketArr.length;i++){
            System.out.println(Arrays.toString(bucketArr[i]));
        }
    }

    /**
     * 获取步长（每个桶最多存放元素个数）
     * @param arr
     * @param bucketNum  桶个数
     * @return
     */
    private static int getStep(int[] arr,int bucketNum){
        int length = getMax(arr)-getMin(arr)+1;
        // 这里要向上取整
        return (int)Math.ceil(length*1.0 / bucketNum);
    }

    /**
     * 获取最大值
     * @param arr
     * @return
     */
    private static int getMin(int[] arr){
        int min=arr[0];
        for(int i=1;i<arr.length;i++){
            if(min>arr[i]){
                min=arr[i];
            }
        }
        return min;
    }

    /**
     * 获取最小值
     * @param arr
     * @return
     */
    private static int getMax(int[] arr){
        int max=arr[0];
        for(int i=1;i<arr.length;i++){
            if(max<arr[i]){
                max=arr[i];
            }
        }
        return max;
    }
}
